package com.zhugang.week10;

/**
 * @program algorithms
 * @description: bages
 * @author: chanzhugang
 * @create: 2022/08/28 20:31
 */
public class BagesByBacktrack {

    /**
     * 0-1背包，试用备忘录解决重复子问题
     * 回溯解法
     */
    // 结果放入maxW
    private int maxW = Integer.MIN_VALUE;
    // 物品重量
    private int[] weight = {2, 2, 4, 6, 3};
    // 物品个数
    private int n = 5;
    // 背包承受的最大重量
    private int w = 9;
    // 备忘录
    private boolean[][] mem = new boolean[5][10];

    public void f(int i, int cw) {
        if (cw == w || i == n) {
            // 装满了 或者 物品都考察完了
            if (cw > maxW) {
                maxW = cw;
            }
            return;
        }
        if (mem[i][cw]) {
            return;
        }
        mem[i][cw] = true;
        // 不装第i个物品
        f(i + 1, cw);
        if (cw + weight[i] <= w) {
            // 装第i个物品
            f(i + 1, weight[i]);
        }
    }
}